{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Node From End of List LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthToLast"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #返回倒数第 k 个节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题稍作改动</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> 1-&gt;2-&gt;3-&gt;4-&gt;5 和 <em>k</em> = 2\n",
    "<strong>输出： </strong>4</pre>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<p>给定的 <em>k</em>&nbsp;保证是有效的。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-node-from-end-of-list-lcci](https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-node-from-end-of-list-lcci](https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        \"\"\"\n",
    "        解题思路：一个指针先走k步，第二个指针和第一个指针都开始走，第一个指针走到链表末尾时，第二个指针正好指向单链表的倒数第\n",
    "        k个节点\n",
    "        \"\"\"\n",
    "        p1 = head\n",
    "        # p1先走k步\n",
    "        for i in range(k):\n",
    "            p1 = p1.next\n",
    "        p2 = head\n",
    "        while p1:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return p2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p = head\n",
    "        q = head.next\n",
    "        p.next = None\n",
    "\n",
    "        while q:\n",
    "            q.next, p, q = p, q, q.next\n",
    "        for i in range(k-1):\n",
    "            p = p.next\n",
    "        return p.val\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        first, second = head, head\n",
    "        for i in range(k):\n",
    "            first = first.next\n",
    "        while first:\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "        return second.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        node = head\n",
    "        for _ in range(k):\n",
    "            node = node.next\n",
    "        while node:\n",
    "            node,head = node.next, head.next\n",
    "        return head.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre=cur=head\n",
    "        for i in range(k):\n",
    "            pre=pre.next\n",
    "        while pre:\n",
    "            pre=pre.next\n",
    "            cur=cur.next\n",
    "        return cur.val\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p1 = head\n",
    "        p2 = head\n",
    "\n",
    "        i = 0\n",
    "        while p1:\n",
    "            p1 = p1.next\n",
    "            i = i+1\n",
    "        \n",
    "        for _ in range(i - k):\n",
    "            p2 = p2.next\n",
    "        \n",
    "        return p2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        d = []\n",
    "        c = head\n",
    "        while c:\n",
    "            d.append(c.val)\n",
    "            c = c.next\n",
    "        \n",
    "        return d[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        right = head\n",
    "        for _ in range(k):\n",
    "            right = right.next\n",
    "\n",
    "        left = head\n",
    "        while right:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "\n",
    "        return left.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p1, p2, = head, head\n",
    "        for _ in range(k):\n",
    "            p1 = p1.next\n",
    "        while p1:\n",
    "            p2 = p2.next\n",
    "            p1 = p1.next\n",
    "        return p2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        stack = []\n",
    "        while head:\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        return stack[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        cur = head\n",
    "        pre = head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "        return pre.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        left, right = head, head\n",
    "        for i in range(k-1):\n",
    "            right = right.next\n",
    "        while right.next:\n",
    "            right = right.next\n",
    "            left = left.next\n",
    "        return left.val\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        if head is None or k==0:\n",
    "            return\n",
    "        tmp = head\n",
    "        for i in range(k):\n",
    "            if head is None:\n",
    "                return None\n",
    "            head = head.next\n",
    "        \n",
    "        while(head):\n",
    "            tmp = tmp.next\n",
    "            head = head.next\n",
    "        \n",
    "        return tmp.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        slow = head\n",
    "        quick = head\n",
    "        # 让快指针先走k步\n",
    "        for i in range(k):\n",
    "            quick = quick.next\n",
    "        # 两个指针一起走\n",
    "        while quick:\n",
    "            slow = slow.next\n",
    "            quick = quick.next\n",
    "        # 当快指针指向空结点时（最后一个结点的后继节点），慢指针就指向倒数第k个结点了 ,直接返回慢结点的值  \n",
    "        return slow.val \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        ptr1, ptr2 = head, head\n",
    "        while k:\n",
    "            ptr2 = ptr2.next\n",
    "            k -= 1\n",
    "        while ptr2:\n",
    "            ptr1 = ptr1.next\n",
    "            ptr2 = ptr2.next\n",
    "        return ptr1.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        f, s = head, head\n",
    "        while k > 0:\n",
    "            f = f.next\n",
    "            k -= 1\n",
    "        while f is not None:\n",
    "            f = f.next\n",
    "            s = s.next\n",
    "        \n",
    "        return s.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "\n",
    "        # 1. 快指针先走到第k个节点\n",
    "        fast = head\n",
    "        while k:\n",
    "            fast = fast.next\n",
    "            k -= 1\n",
    "        \n",
    "        # 2. 慢指针从头出发，快指针从第k个节点出发，此时快指针走完之后，慢指针所在节点就是倒数第n个节点\n",
    "        slow = head\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre,cur = head,head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        return pre.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for _ in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        return pre.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = slow = head\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast :\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre, cur = pre.next, cur.next\n",
    "        return pre.val\n",
    "        # length = 0\n",
    "        # cur1 = head\n",
    "        # while cur1:\n",
    "        #     cur1 = cur1.next\n",
    "        #     length += 1\n",
    "        # print(length)\n",
    "        # num = 0\n",
    "        # cur2 = head\n",
    "        # while cur2:\n",
    "        #     if num == length - k:\n",
    "        #         return cur2.val\n",
    "        #     num += 1\n",
    "        #     cur2 = cur2.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        if not head:\n",
    "            return None\n",
    "        dummy = ListNode(0 , head)\n",
    "        slow , fast = dummy , dummy\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        arr = []\n",
    "        while head:\n",
    "            arr.append(head.val)\n",
    "            head = head.next\n",
    "        return arr[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        \n",
    "        # if not head.next:\n",
    "        #     return head.val\n",
    "        \n",
    "        res = [head.val]\n",
    "        cnt=0\n",
    "\n",
    "        pre,cur = head,head\n",
    "        while cur.next:\n",
    "            pre,cur=pre.next,cur.next\n",
    "            res.append(pre.val)\n",
    "            cnt+=1\n",
    "        print(res)\n",
    "        \n",
    "\n",
    "        return res[cnt-k+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = head\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            head = head.next\n",
    "        return head.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        # 递归\n",
    "        # if head == None:\n",
    "        #     return\n",
    "        # reverse = self.traverse(head)\n",
    "        \n",
    "        # n = 1\n",
    "        # while n < k:\n",
    "        #     reverse = reverse.next\n",
    "        #     n += 1\n",
    "        # return reverse.val\n",
    "        # 双指针\n",
    "        p1 = head\n",
    "        for i in range(k):\n",
    "            p1 = p1.next\n",
    "        p2 = head\n",
    "        while p1:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return p2.val\n",
    "    \n",
    "    def traverse(self,head):\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        last = self.traverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        length = 0\n",
    "        cur1 = head\n",
    "        while cur1:\n",
    "            cur1 = cur1.next\n",
    "            length += 1\n",
    "        print(length)\n",
    "        num = 0\n",
    "        cur2 = head\n",
    "        while cur2:\n",
    "            if num == length - k:\n",
    "                return cur2.val\n",
    "            num += 1\n",
    "            cur2 = cur2.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        result = list()\n",
    "        while head:\n",
    "            result.append(head.val)\n",
    "            head = head.next\n",
    "        return result[len(result)-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast, slow = head, head\n",
    "        for i in range(k-1):\n",
    "            fast = fast.next\n",
    "        while fast.next is not None:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        kth_back = head\n",
    "        while head:\n",
    "            if not k:\n",
    "                kth_back = kth_back.next\n",
    "            else:\n",
    "                k -= 1\n",
    "            head = head.next\n",
    "        \n",
    "        return kth_back.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p1, p2 = head, head\n",
    "        for _ in range(k - 1):\n",
    "            p2 = p2.next\n",
    "        while p2.next:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return p1.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        a=head\n",
    "        b=head\n",
    "        for i in range(k):\n",
    "            b=b.next\n",
    "        while b:\n",
    "            a=a.next\n",
    "            b=b.next\n",
    "        return a.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        if not head:\n",
    "            return None\n",
    "        ptr1, ptr2 = head, head\n",
    "        while k:\n",
    "            ptr2 = ptr2.next\n",
    "            k -= 1\n",
    "        while ptr2:\n",
    "            ptr1 = ptr1.next\n",
    "            ptr2 = ptr2.next\n",
    "        return ptr1.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre, cur = pre.next, cur.next\n",
    "        return pre.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        low,fast = head, head\n",
    "        while k:\n",
    "            fast = fast.next\n",
    "            k -= 1\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            low = low.next\n",
    "        return low.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        # for i in range(k):\n",
    "        #     cur = cur.next\n",
    "        # while cur:\n",
    "        #     pre, cur = pre.next, cur.next\n",
    "        # return pre.val\n",
    "        counts1, counts2 = 0, 0\n",
    "        while  pre:\n",
    "            counts1 += 1\n",
    "            pre = pre.next\n",
    "        #print(counts1)\n",
    "        while  cur:\n",
    "            \n",
    "            if(counts2 == counts1-k):\n",
    "                return cur.val\n",
    "            cur = cur.next\n",
    "            counts2 += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        fast = dummy\n",
    "        slow = dummy\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        slow,fast = head,head\n",
    "        while k:\n",
    "            fast = fast.next\n",
    "            k -= 1\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre, cur = pre.next, cur.next\n",
    "        return pre.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        dummy = ListNode(-1, head)\n",
    "        x = self.findKNode(dummy, k)   \n",
    "        return x.val\n",
    "    def findKNode(self, head, x):\n",
    "        p = head\n",
    "        for _ in range(x):\n",
    "            p = p.next\n",
    "        q = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        a = head\n",
    "        b = head\n",
    "        for i in range(k):\n",
    "            a = a.next\n",
    "        while a:\n",
    "            a = a.next\n",
    "            b = b.next\n",
    "        return b.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int):\n",
    "        h1 = head\n",
    "        for i in range(k):\n",
    "            h1 = h1.next\n",
    "        h2 = head\n",
    "        while h1 != None:\n",
    "            h1 = h1.next\n",
    "            h2 = h2.next\n",
    "        return h2.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        n = 0\n",
    "        i = 0\n",
    "        tmp = head\n",
    "        tmp1 = head\n",
    "        while tmp:\n",
    "            tmp = tmp.next\n",
    "            n += 1\n",
    "        while i < n-k:\n",
    "            tmp1 = tmp1.next\n",
    "            i += 1\n",
    "        return tmp1.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pf = pl = head\n",
    "        for _ in range(k):\n",
    "            pf = pf.next\n",
    "        while pf:\n",
    "            pf = pf.next\n",
    "            pl = pl.next   \n",
    "        return pl.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        front = head\n",
    "        while k-1 > 0:\n",
    "            front = front.next\n",
    "            k -= 1\n",
    "        \n",
    "        start = head\n",
    "        while front.next:\n",
    "            front = front.next\n",
    "            start = start.next\n",
    "        \n",
    "        return start.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = slow = head\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        count = 0\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            count += 1\n",
    "        total = 2 * count\n",
    "        if fast is not None:\n",
    "            total += 1\n",
    "        target = total - k\n",
    "        for i in range(target):\n",
    "            head = head.next\n",
    "        return head.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        h = head\n",
    "        q = head\n",
    "        for i in range(k):\n",
    "            q = q.next\n",
    "        while q:\n",
    "            q = q.next\n",
    "            h = h.next\n",
    "        return h.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        visited = list()\n",
    "        curr = head\n",
    "        while curr:\n",
    "            visited.append(curr.val)\n",
    "            curr = curr.next\n",
    "        return visited[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        stack = []\n",
    "        while head:\n",
    "            stack.append(head)\n",
    "            head = head.next\n",
    "        return (stack[-k]).val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        l=0\n",
    "        rot=ListNode(0);rot.next=head\n",
    "        while(head):l+=1;head=head.next\n",
    "        l-=k;head=rot.next\n",
    "        while(l):l-=1;head=head.next\n",
    "        return head.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for i in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre, cur = pre.next, cur.next\n",
    "        return pre.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        nums = []\n",
    "        p = head\n",
    "        while p:\n",
    "            nums.append(p.val)\n",
    "            p = p.next\n",
    "        return nums[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast, slow = 0, 0\n",
    "        node, res = head, head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            fast += 1\n",
    "            if fast > k:\n",
    "                res = res.next\n",
    "        return res.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p, q = head ,head\n",
    "        for _ in range(k):\n",
    "            p = p.next\n",
    "        while p:\n",
    "            p ,q = p.next, q.next\n",
    "        return q.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre = head\n",
    "        rear = pre\n",
    "        for _ in range(k-1):\n",
    "            rear = rear.next\n",
    "        \n",
    "        while(rear.next):\n",
    "            pre = pre.next\n",
    "            rear = rear.next\n",
    "        \n",
    "        return pre.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        for _ in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "    \n",
    "       \n",
    "       a=0\n",
    "       cur=head\n",
    "       while cur:\n",
    "         a+=1\n",
    "         cur=cur.next\n",
    "       b=a-k\n",
    "       while b>0:\n",
    "          head=head.next\n",
    "          b-=1\n",
    "       return head.val "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        slow = fast = head\n",
    "        for _ in range(k):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        cur = head\n",
    "        n = 0\n",
    "        while head != None :#先让head走k步，然后head和cur一起走，直到head链表为None，cur所在位置就是元素位置，然后返回cur\n",
    "            if n>= k:\n",
    "                cur = cur.next\n",
    "            head = head.next\n",
    "            n += 1\n",
    "        return cur.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        dummyHead = ListNode(0, head)\n",
    "        slow, fast = dummyHead, head\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "      \n",
    "        #slow.next = slow.next.next\n",
    "        #return dummyHead.next\n",
    "        return slow.next.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        cur1, cur2 = head, head\n",
    "        for _ in range(k):\n",
    "            cur2 = cur2.next\n",
    "        while cur2:\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        return cur1.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre, cur = head, head\n",
    "        for _ in range(k):\n",
    "            cur = cur.next\n",
    "        while cur:\n",
    "            pre, cur = pre.next, cur.next\n",
    "        return pre.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        p1=head\n",
    "        for i in range(k):\n",
    "            p1=p1.next\n",
    "        p2=head\n",
    "        while(p1):\n",
    "            p1=p1.next\n",
    "            p2=p2.next\n",
    "        return p2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        dummy = ListNode(val=0, next=head)\n",
    "        for _ in range(k):\n",
    "           dummy = dummy.next\n",
    "        while dummy.next is not None:\n",
    "            head = head.next\n",
    "            dummy = dummy.next\n",
    "        return head.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        pre = head\n",
    "        after = head\n",
    "        for i in range(k):\n",
    "            after = after.next\n",
    "        while after:\n",
    "            pre = pre.next\n",
    "            after = after.next \n",
    "        return pre.val\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        result = []\n",
    "        index = 0\n",
    "        while head:\n",
    "            result.append(head.val)\n",
    "            index += 1\n",
    "            head = head.next\n",
    "        result_reserve = result[::-1]\n",
    "        \n",
    "        return result_reserve[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        res=head\n",
    "        for i in range(k-1):\n",
    "            head=head.next\n",
    "        while head.next!=None:\n",
    "            head=head.next\n",
    "            res=res.next\n",
    "        return res.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        slow, fast = head, head\n",
    "        for i in range(k):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        gap = 1\n",
    "        while fast.next:\n",
    "            if gap == k:\n",
    "                slow = slow.next\n",
    "            else:\n",
    "                gap += 1\n",
    "            fast = fast.next\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        if not head or k <= 0:\n",
    "            return head\n",
    "\n",
    "        fast = head\n",
    "        slow = head\n",
    "\n",
    "        for i in range(k-1):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            print('fast-->',fast.val)\n",
    "        # print('slow-->',slow.val)\n",
    "        # print('fast-->',fast.val)\n",
    "        return slow.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        # 快慢指针\n",
    "        prev, last = head, head\n",
    "        for idx in range(k):\n",
    "            prev = prev.next\n",
    "\n",
    "        while prev:\n",
    "            prev = prev.next\n",
    "            last = last.next\n",
    "        return last.val\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def kthToLast(self, head: ListNode, k: int) -> int:\n",
    "        cnt=0\n",
    "        fast=head\n",
    "        while k and fast:\n",
    "            fast=fast.next\n",
    "            k-=1\n",
    "        slow=head\n",
    "        while fast:\n",
    "            fast=fast.next\n",
    "            slow=slow.next\n",
    "        return slow.val\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
